/*
 * @Author: your name
 * @Date: 2021-10-12 10:32:40
 * @LastEditTime: 2021-10-12 11:20:32
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \luogu\动态规划\模板问题\P1060 开心的金明\temp.cpp
 */
#include <iostream>
#include<algorithm>
using namespace std;
const int N = 27, M = 30010;
int f[N][M];
int v[N], w[N];

int main(void)
{
    int n, m;
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
    {
        int V, p;
        cin >> V >> p;
        v[i] = V;
        w[i] = V * p;
    }
    
    //n是 物品个数
    for(int i = 1; i <= n; i++)
    {
        //当前可以花的钱数
        for(int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    
    cout << f[n][m] << endl;
    return 0;
}
